#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <random>
using std::cout;
using std::endl;
using std::vector;
using std::string;

template <typename T>
struct Edge {
    size_t src;
    size_t dest;
    T weight;
    inline bool operator<(const Edge<T>& that) const {
        return weight < that.weight;
    }
    inline bool operator>(const Edge<T>& that) const {
        return weight < that.weight;
    }
};

//为了简便，每次设置图的大小时都比实际定点数+1
template <typename T>
class Graph {
public:
    Graph(size_t N): vertices_(N) {}
    auto vertices() const { return vertices_; }
    const auto& edges() const { return edgeList_; }
    void addEdge(const Edge<T>& e) {
        if (e.src >= 1 && e.src <= vertices_ && e.dest >= 1 && e.dest <= vertices_)
            edgeList_.emplace_back(e);
        else
            std::cerr << "Edge out of range\n";
    }
    void addEdge(Edge<T>&& e) {
        if (e.src >= 1 && e.src <= vertices_ && e.dest >= 1 && e.dest <= vertices_)
            edgeList_.emplace_back(std::move(e));
        else
            std::cerr << "Edge out of range\n";
    }
    auto edgesFromVertex(size_t v) const {
        vector<Edge<T>> edgesRet;
        for (const auto& e : edgeList_) {
            if (e.src == v)
                edgesRet.emplace_back(e);
        }
        return edgesRet;
    }
    friend std::ostream& operator<<(std::ostream& os, const Graph<T>& G) {
        for (size_t i = 1; i < G.vertices(); ++i) {
            auto edges = G.edgesFromVertex(i);
            os << "Vertex[" << i << "]:\t";
            for (const auto& e : edges) {
                os << "{" << e.dest << ", " << e.weight << "}, ";
            }
            os << endl;
        }
        return os;
    }
private:
    size_t vertices_; //顶点数
    vector<Edge<T>> edgeList_; //所有边的数组
};


#endif // __GRAPH_H__